<?php
// https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484500&idx=1&sn=83f4df1253f597898b2f74ea9dca9fd9&chksm=9bd7fa5caca0734ad182ba67651882647a71264938eaa98e49c5ff43369b807a094ad16efcd4&scene=178&cur_album_id=1318896187793260544#rd

class LRUCache {
    private $map;
    private $linked_list;
    private $capacity;

    /**
     * @param Integer $capacity
     */
    function __construct($capacity) {
        $this->map = array();
        $this->linked_list = new LinkedList();
        $this->capacity = $capacity;
    }

    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key) {
        if (! isset($this->map[$key])) {
            return -1;
        }

        // 将该数据提升为最近使用的
        $this->makeRecently($key);

        return $this->map[$key]->val;
    }

    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value)
    {
        if (isset($this->map[$key])) {
            // 删除旧的数据
            $this->deleteKey($key);

            // 新插入的数据为最近使用的数据
            $this->addRecently($key, $value);

            return;
        }

        // 容量达到上限
        if ($this->capacity == count($this->map)) {
            // 删除最久未使用的元素
            $this->removeLeastRecently();
        }

        // 添加为最近使用的元素
        $this->addRecently($key, $value);
    }

    /**
     *  将某个 key 提升为最近使用的
     * @param $key
     */
    private function makeRecently($key)
    {
        $x = $this->map[$key];

        // 先从链表中删除这个节点
        $this->linked_list->remove($x);

        // 重新插到队尾
        $this->linked_list->addLast($x);
    }

    /**
     * 添加最近使用的元素
     * @param $key
     * @param $val
     */
    private function addRecently($key, $val)
    {
        $x = new Node($key, $val);

        // 链表尾部就是最近使用的元素
        $this->linked_list->addLast($x);

        // 别忘了在 map 中添加 key 的映射
        $this->map[$key] = $x;
    }

    /**
     * 删除某一个 key
     * @param int $key
     */
    private function deleteKey($key) {
        $x = $this->map[$key];

        // 从链表中删除
        $this->linked_list->remove($x);

        // 从 map 中删除
        unset($this->map[$key]);
    }

    /**
     * 删除最久未使用的元素
     */
    private function removeLeastRecently() {
        // 链表头部的第一个元素就是最久未使用的
        $deletedNode = $this->linked_list->removeFirst();

        // 同时别忘了从 map 中删除它的 key
        $deletedKey = $deletedNode->key;

        unset($this->map[$deletedKey]);
    }
}

class LinkedList
{
    // 头尾虚节点
    private  $head;
    private  $tail;

    // 链表元素数
    private $size;

    public function __construct()
    {
        $head = new Node(0, 0);
        $tail = new Node(0, 0);

        $this->head = $head;
        $this->tail = $tail;

        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }

    // 在链表尾部添加节点 x，时间 O(1)
    public function addLast(Node $x)
    {
        $x->prev = $this->tail->prev;

        $x->next = $this->tail;

        $this->tail->prev->next = $x;

        $this->tail->prev = $x;

        $this->size++;
    }

    // 删除链表中的 x 节点（x 一定存在）
    // 由于是双链表且给的是目标 Node 节点，时间 O(1)
    public function remove(Node $x)
    {
        $x->prev->next = $x->next;

        $x->next->prev = $x->prev;

        $this->size--;
    }

    // 删除链表中第一个节点，并返回该节点，时间 O(1)
    public function removeFirst()
    {
        if ($this->head->next == $this->tail) {
            return null;
        }

        $first = $this->head->next;

        $this->remove($first);

        return $first;
    }

    // 返回链表长度，时间 O(1)
    public function size()
    {
        return $this->size;
    }
}

class Node {
    public $key;
    public $val;

    public $next;
    public $prev;

    public function __construct($k, $v)
    {
        $this->key = $k;
        $this->val = $v;
    }
}